#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include  <stdlib.h>
struct ListNode
{
	int val;
	struct ListNode* next;
};

struct ListNode* partition(struct ListNode* phead, int x)
{
	struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;
	lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
	greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
	lesstail->next = greatertail->next = NULL;
	struct ListNode* cur = phead;
	while (cur)
	{
		if (cur->val < x)
		{
			lesstail->next = cur;
			lesstail = lesstail->next;
		}
		else
		{
			greatertail->next = cur;
			greatertail = greatertail->next;
		}
		cur = cur->next;
	}
	lesstail->next = greaterhead->next;
	greatertail->next = NULL;
	phead = lesshead->next;
	free(lesshead);
	free(greaterhead);
	return phead;
}
struct ListNode* CreateList(int* a, int n)
{
	struct  ListNode* phead = NULL, * ptail = NULL;
	int x = 0;
	for (int i = 0; i < n; ++i)
	{
		struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
		if (newnode == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		else
		{
			newnode->val = a[i];
			newnode->next = NULL;
		}
		if (phead == NULL)
		{
			ptail = phead = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}
int main()
{
	int a[] = { 2,3,9,1,6,8 };
	struct ListNode* plist = CreateList(a, sizeof(a) / sizeof(int));
	partition(plist, 5);
	return 0;
}